package com.zcmyth.collection;

import java.util.Stack;

import com.zcmyth.util.Pair;

public class MinStack<T extends Comparable<T>> extends Stack<T> {

  private static final long serialVersionUID = -2075791026849968462L;

  private Stack<Pair<Integer, T>> mins;

  public MinStack() {
    super();
    mins = new Stack<Pair<Integer, T>>();
  }

  @Override
  public T push(T item) {
    if (mins.isEmpty() || item.compareTo(mins.peek().getSecond()) < 0) {
      mins.push(new Pair<Integer, T>(size(), item));
    }
    return super.push(item);
  }

  @Override
  public T pop() {
    if (!mins.isEmpty() && mins.peek().getFirst() == (size() - 1)) {
      mins.pop();
    }
    return super.pop();
  }

  public T min() {
    return mins.isEmpty() ? null : mins.peek().getSecond();
  }

}
